package ru.usu.gv.utils.geometry;

import javax.vecmath.Point2d;
import javax.vecmath.Point3d;
import javax.vecmath.Vector2d;

import java.util.List;

/**
 * @author spupyrev
 * 29.10.2009
 */
public class Polygon
{
	//Points is counterclockwise!!!
	private Polyline polyline;

	public Polygon(Polyline polyline)
	{
		this.polyline = polyline;
		orientCCW();
	}

	private void orientCCW()
	{
		if (polyline.isCW())
			polyline.reverse();
	}

	public Point3d[] toControlPoints()
	{
		List<Point2d> points = polyline.getPoints();
		Point3d[] result = new Point3d[points.size() + 1];
		for (int i = 0; i < result.length; i++)
		{
			Point2d p = points.get(i % points.size());
			result[i] = new Point3d(p.x, p.y, 0);
		}
		return result;
	}

	public List<Point2d> getPoints()
	{
		return polyline.getPoints();
	}

	public boolean intersect(Polyline polyline)
	{
		for (int i = 0; i + 1 < polyline.getPoints().size(); i++)
			if (intersect(polyline.getPoints().get(i), polyline.getPoints().get(i + 1)))
				return true;

		return false;
	}

	/**
	 *  stolen from http://softsurfer.com/Archive/algorithm_0111/algorithm_0111.htm 
	 */
	public boolean intersect(Point2d p0, Point2d p1)
	{
		if (p1.equals(p0))
		{
			return contains(p0);
		}

		double tE = 0; // the maximum entering segment parameter
		double tL = 1; // the minimum leaving segment parameter
		Vector2d dS = new Vector2d();
		dS.sub(p1, p0);

		for (int i = 0; i < polyline.getPoints().size(); i++) // process polygon edge V[i]V[i+1]
		{
			Vector2d e = new Vector2d(polyline.getPoints().get((i + 1) % polyline.getPoints().size()));
			e.sub(polyline.getPoints().get(i));
			Vector2d pv = new Vector2d();
			pv.sub(p0, polyline.getPoints().get(i));
			double N = e.x * pv.y - e.y * pv.x;
			double D = -(e.x * dS.y - e.y * dS.x);
			if (Math.abs(D) < 1e-8)
			{ // S is nearly parallel to this edge
				if (N <= 0) // P0 is outside this edge, so
					return false; // S is outside the polygon
				else
					// S cannot cross this edge, so
					continue; // ignore this edge
			}

			double t = N / D;
			if (D < 0)
			{ // segment S is entering across this edge
				if (t > tE)
				{ // new max tE
					tE = t;
					if (tE > tL) // S enters after leaving polygon
						return false;
				}
			}
			else
			{ // segment S is leaving across this edge
				if (t < tL)
				{ // new min tL
					tL = t;
					if (tL < tE) // S leaves before entering polygon
						return false;
				}
			}
		}

		if (Math.abs(tE - tL) < 1e-8)
			return false;

		Point2d i0 = new Point2d();
		i0.scaleAdd(tE, dS, p0);
		Point2d i1 = new Point2d();
		i1.scaleAdd(tL, dS, p0);

		//System.out.println("Start: " + i0 + "  End: " + i1);

		return true;
	}

	public boolean contains(Point2d point)
	{
		int wn = 0;
		// Проверить, не совпадает ли точка с одной из вершин
		for (Point2d v : getPoints())
			if (v.equals(point))
				return false;

		// Проверить, не лежит ли точка на одной из сторон
		for (int i = 0; i < getPoints().size(); i++)
		{
			Point2d pi = getPoints().get(i);
			Point2d pi1 = getPoints().get((i + 1) % getPoints().size());
			if (cross(pi, pi1, point) == 0 && Math.abs(Math.abs(pi.x - pi1.x) - Math.abs(pi.x - point.x) - Math.abs(pi1.x - point.x)) < 1e-8
					&& Math.abs(Math.abs(pi.y - pi1.y) - Math.abs(pi.y - point.y) - Math.abs(pi1.y - point.y)) < 1e-8)
				return false;
		}
		// Метод Winding-Number
		for (int i = 0; i < getPoints().size(); i++)
		{
			Point2d pi = getPoints().get(i);
			Point2d pi1 = getPoints().get((i + 1) % getPoints().size());

			if (pi.y < point.y + 1e-8 && pi1.y > point.y + 1e-8)
			{
				if (cross(pi, pi1, point) > 0)
					wn++;
			}
			else if (pi.y > point.y + 1e-8 && pi1.y < point.y + 1e-8)
			{
				if (cross(pi, pi1, point) < 0)
					wn--;
			}
		}
		return (wn != 0);
	}

	private int cross(Point2d p0, Point2d p1, Point2d p2)
	{
		double cr = (p1.x - p0.x) * (p2.y - p0.y) - (p1.y - p0.y) * (p2.x - p0.x);
		if (cr < -1e-8)
			return -1;
		if (cr > 1e-8)
			return 1;
		return 0;
	}

}
